Thuật toán xuất phát từ một cây chỉ chứa đúng một đỉnh và mở rộng từng bước một, mỗi bước thêm một cạnh mới vào cây, cho tới khi bao trùm được tất cả các đỉnh của đồ thị.

• Dữ liệu vào: Một đồ thị có trọng số liên thông với tập hợp đỉnh V và tập hợp cạnh E (trọng số có thể âm). Đồng thời cũng dùng V và E để ký hiệu số đỉnh và số cạnh của đồ thị.
• Khởi tạo: Vmới = {x}, trong đó x là một đỉnh bất kì (đỉnh bắt đầu) trong V, Emới = {}
• Lặp lại cho tới khi Vmới = V:
  • Chọn cạnh (u, v) có trọng số nhỏ nhất thỏa mãn u thuộc Vmới và v không thuộc Vmới (nếu có nhiều cạnh như vậy thì chọn một cạnh bất kì trong chúng)
  • Thêm v vào Vmới, và thêm cạnh (u, v) vào Emới
• Dữ liệu ra: Vmới và Emới là tập hợp đỉnh và tập hợp cạnh của một cây bao trùm nhỏ nhất